﻿#pragma once
// 公共部分
#include <iostream>
#include <vector>

#include <time.h>
#include <assert.h>

#include <thread>
#include <mutex>

static const size_t MAX_BYTES = 256 * 1024;
static const size_t NFREELIST = 208;

// 条件编译：32位环境下页表id用size_t就能存下，而64位环境下页表id需要用unsigned long long
#ifdef _WIN64
typedef unsigned long long PAGE_ID;
// 在win32环境下有_WIN32宏的定义，在win64环境下既有_WIN32又有_WIN64，所以要把判断_WIN64的条件放在前面，否则碰到_WIN32就直接编译了
#elif _WIN32
typedef size_t PAGE_ID;
#else
// 其他环境
#endif

// 获取头四个/八个字节的内容（指向的地址）
static void*& NextObj(void*& obj)
{
	return *(void**)obj;
}

// 管理切分好的小对象的自由链表
class FreeList
{
public:
	void Push(void* obj)
	{
		assert(obj);
		// 头插
		// *(void**)obj = _freeList;
		NextObj(obj) = _freeList;
		_freeList = obj;
	}

	void PushRange(void* start, void* end)
	{
		NextObj(end) = _freeList;
		_freeList = start;
	}

	void* Pop()
	{
		assert(_freeList);
		// 头删
		void* obj = _freeList;
		_freeList = NextObj(obj);
		return obj;
	}

	bool Empty()
	{
		return _freeList == nullptr;
	}

	size_t& MaxSize()
	{
		return _maxSize;
	}
private:
	void* _freeList = nullptr;
	size_t _maxSize = 1;
};

// 内存块大小映射规则
class SizeClass
{
private:
	// 整体控制在最多10%左右的内碎片浪费
	// [1,128]					8byte对齐      	freelist[0,16)
	// [128+1,1024]				16byte对齐  		freelist[16,72)
	// [1024+1,8*1024]			128byte对齐  	freelist[72,128)
	// [8*1024+1,64*1024]		1024byte对齐     freelist[128,184)
	// [64*1024+1,256*1024]		8*1024byte对齐   freelist[184,208)
	
	// 常规对齐方法
	//size_t _RoundUp(size_t size, size_t alignNum) // 参数：大小，对齐数
	//{
	//	if (size % alignNum == 0) return size; // 如果等于对齐数，不做处理
	//	return (size / alignNum + 1) * alignNum; // 不等于对齐数，向上对齐
	//}

	// 改进
	static inline size_t _RoundUp(size_t size, size_t alignNum)
	{
		// size + alignNum - 1 ：size加上对齐数减1
		// & ~(alignNum - 1) ：把该数的对齐数低位去掉，即为对齐数
		return ((size + alignNum - 1) & ~(alignNum - 1));
	}

	// 常规
	//static inline size_t _Index(size_t size, size_t alignNum)
	//{
	//	if (size % alignNum == 0) return size / alignNum - 1;
	//	else return size / alignNum;
	//}

	// 改进
	static inline size_t _Index(size_t size, size_t align_shift /*对齐数转成二进制后低位0的个数*/)
	{
		// 1 << align_shift 为对齐数
		// (size + (1 << align_shift) - 1) size加上对齐数减1
		// (size + (1 << align_shift) - 1) >> align_shift 把对齐数低位的数字忽略，得出的就是第n个对齐数
		// 因为是从0开始，所以再减1
		return ((size + (1 << align_shift) - 1) >> align_shift) - 1;
	}

	// 是否可行？？
	//static inline size_t _Index(size_t size, size_t alignNum)
	//{
	//	return (size - 1) / alignNum - 1;
	//}

public:
	// 计算对齐数
	static inline size_t RoundUp(size_t size) // 写成静态可以不通过对象直接访问
	{
		if (size <= 128)
			return _RoundUp(size, 8);
		else if (size <= 1024)
			return _RoundUp(size, 16);
		else if (size <= 8 * 1024)
			return _RoundUp(size, 128);
		else if (size <= 64 * 1024)
			return _RoundUp(size, 1024);
		else if (size <= 256 * 1024)
			return _RoundUp(size, 8 * 1024);
		else
		{
			assert(false);
			return -1;
		}
	}

	// 计算每个数映射的哪个个桶
	static inline size_t Index(size_t size)
	{
		// 每个区间有多少桶
		static int group_array[4] = { 16, 56, 56, 56 };
		if (size <= 128)
			return _Index(size, 3);
		else if (size <= 1024)
			return _Index(size - 128, 4) + group_array[0];
		else if (size <= 8 * 1024)
			return _Index(size - 1024, 7) + group_array[0] + group_array[1];
		else if (size <= 64 * 1024)
			return _Index(size - 8 * 1024, 10) + group_array[0] + group_array[1] + group_array[2];
		else if (size <= 256 * 1024)
			return _Index(size - 64 * 1024, 8 * 1024) + group_array[0] + group_array[1] + group_array[2] + group_array[3];
		else
		{
			assert(false);
			return -1;
		}
	}

	// 每次从中心内存获取多少块小内存对象
	static size_t NumMoveSize(size_t size)
	{
		if (size == 0)
			return 0;
		// [2, 512]，一次批量移动多少个对象的(慢启动)上限值
		// 小对象一次批量上限高
		// 小对象一次批量上限低
		int num = MAX_BYTES / size;
		if (num < 2)
			num = 2;
		if (num > 512)
			num = 512;
		return num;
	}

};

// 管理多个连续页大块内存跨度结构
struct Span
{
	PAGE_ID _pageId = 0;		// 起始页号
	size_t _n = 0;				// 页数

	Span* _prev = nullptr;		// 双向链表的指针
	Span* _next = nullptr;

	size_t _usecount = 0;		// 分配出去的小块内存的计数
	void* _freeList = nullptr;	// 切好内存的自由链表
};

// 带头双向循环链表
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_prev = _head;
		_head->_next = _head;
	}

	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);

		newSpan->_prev = pos->_prev;
		newSpan->_next = pos;
		newSpan->_prev->_next = newSpan;
		pos ->_prev = newSpan;
	}

	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);

		pos->_prev->_next = pos->_next;
		pos->_next->_prev = pos->_prev;
	}

	void Lock()
	{
		_mtx.lock();
	}

	void Unlock()
	{
		_mtx.unlock();
	}
private:
	Span* _head;
	std::mutex _mtx; // 桶锁
};